МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД
«УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»
Інженерно-технічний факультет
Кафедра комп’ютерних систем та мереж
Розрахунково-графічна робота
з дисципліни
«Теоретичні основи ЦОС»
на тему:
«Розрахунок параметрів виконання алгоритму ШПФ»
Завдання
Варіант № 18
Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними:
Кількість точок
4096
Основа ШПФ
2
Прорідження
Частотне
Частота роботи процесора
2,0 МГц
Розрядність вхідних даних
32 (16+16), біт (Re +Im)
Тип вхідного інтерфейсу, пристрою
Link-port
Тип вихідного інтерфейсу, пристрою
SPORT
2
Анотація
В розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 2 для 32-розрядних вхідних даних з частотним прорідженням, детально описано механізми обчислення швидкого перетворення Фур`є за заданною основою, обчислено часові ресурси для виконання обчислення, створена функціональна схема системи та написана програма, що реалізує вказаний алгоритм ШПФ.
Зміст
Вступ 5
1. Теоретичний розділ 6
1.1. Опис ШПФ 6
1.1.1. Основні визначення 6
1.1.2. Властивості повертаючих множників 6
1.1.3. Основні формули 7
2. Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора 9
2.1. Побудова графа алгоритму ШПФ з основою 2 9
2.1.1. Обчислення повертаючих множників WN 10
2.2. Біт інверсний порядок видачі даних 10
2.2.1. Блок-схема перетворення 11
3. Розрахунковий розділ 12
4. Розробка функціональної схеми 14
5. Розробка програми виконання алгоритму ШПФ 15
Висновки 19
Література 20
Вступ
Алгоритм швидкого перетворення Фур’є – є оптимізованим за швидкодією способом обчислення дискретного перетворення Фур’є (ДПФ), що має складність O(Nlog2N) на відміну від складності ДПФ порядку O(N2).
Аналіз Фур’є закладає основи багатьох методів, що застосовуються в області цифрової обробки сигналів (ЦОС). По суті справи, перетворення Фур’є (фактично існує кілька варіантів таких перетворень) дозволяє співставити сигналу, заданому в часовій області, його еквівалентне представлення в частотній області, і навпаки, якщо відома частотна характеристика сигналу, то зворотне перетворення Фур’є дозволяє визначити відповідний сигнал у часовій області.
Крім того, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фур’є його імпульсної реакції. І навпаки, якщо визначена частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотнього перетворення Фур’є над його частотною характеристикою. Цифрові фільтри можуть бути створені на основі їхньої імпульсної реакції, оскільки коефіцієнти фільтра з кінцевою імпульсною характеристикою (КІХ) ідентичні дискретній імпульсній реакції фільтра.
1. Теоретичний розділ
1.1. Опис ШПФ
1.1.1. Основні визначення
Визначення 1. Дано кінцеву послідовність x0, x1, x2,..., xN-1 (у загальному випадку комплексних чисел). ДПФ полягає в пошуку послідовності X0, X1, X2,..., XN-1, елементи якої обчислюються за формулою:
(1)
Визначення 2. Зворотне ДПФ полягає в пошуку послідовності x0, x1, x2,..., xN-1, елементи якої обчислюються за формулою:
(2)
Основною властивістю перетворень (1) і (2) є те, що з послідовності {x} отримується (при прямому перетворенні) послідовність {X}, а якщо застосувати до {X} зворотне перетворення, то знову отримується вихідна послідовність {x}.
Визначення 3. Величина називається повертаючим множником.
1.1.2. Властивості повертаючих множників
При k = 1
Пряме перетворення Фур’є можна виразити через повертаючі множники. Тоді формула (1) матиме вигляд: (3)
Геометричне тлумачення повертаючих множників наведене на рис.1. Комплексне число (rejφ) представлене у вигляді вектора, що виходить із початку координат (r - модуль числа, а φ – аргумент...